package com.le.basic.linked.singleDemo;

import java.util.Stack;

public class singleLinked {

    private SingleNode head = null;

    public SingleNode getHead() {
        return head;
    }

    public void setHead(SingleNode head) {
        this.head = head;
    }

    /**
     * 添加 -->尾插法
     *
     * @param newNode
     */
    public void add(SingleNode newNode) {
        if (head == null) {
            head = newNode;
        } else {
            SingleNode temp = head;
            while (true) {
                if (temp.next == null) {
                    break;
                }
                temp = temp.next;
            }
            temp.next = newNode;
        }
    }

    /**
     * 打印
     */
    public void show() {
        if (this.head == null) {
            return;
        }
        SingleNode temp = this.head;
        while (true) {
            System.out.println(temp.data);
            if (temp.next == null) {
                break;
            }
            temp = temp.next;
        }
    }

    /**
     * 修改数据 按照node.data
     *
     * @param node
     */
    public void update(SingleNode node) {
        if (this.head == null) {
            return;
        }
        boolean flag = false;
        SingleNode temp = head;
        while (true) {
            if (temp.data == node.data) {
                flag = true;
                break;
            }
            if (temp.next == null) {
                flag = false;
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            temp.data = node.data;
        } else {
            System.out.println("not exist");
        }
    }

    /**
     * 按照data删除数据
     *
     * @param data
     */
    public void delete(int data) {
        SingleNode temp = head;
        boolean flag = false;
        while (true) {
            if (temp.data == data) {
                flag = true;
                break;
            }
            if (temp.next == null) {
                flag = false;
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            temp.next = temp.next.next;
        } else {
            System.out.println("待删除的节点不存在");
        }
    }

    /**
     * 按照id查询数据,返回结点信息
     *
     * @param id
     * @return
     */
    public void queryByData(int id) {
        SingleNode temp = head;
        boolean flag = false;
        while (true) {
            if (temp.data == id) {
                flag = true;
                break;
            }
            if (temp.next == null) {
                flag = false;
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            System.out.println(temp);
        } else {
            System.out.println("待查找的节点不存在");
        }
    }

    /**
     * 求单链表中有效节点个数
     *
     * @return
     */
    public int getLength() {
        if (head == null) {
            return 0;
        }
        int count = 0;
        SingleNode temp = head;
        while (true) {
            count++;
            if (temp.next == null) {
                break;
            }
            temp = temp.next;
        }
        return count;
    }

    /**
     * 按顺序插入新节点
     *
     * @param newNode
     */
    public void insert(SingleNode newNode) {
        if (newNode == null) {
            return;
        }
        if (this.head == null) {
            this.head = newNode;
            return;
        }
        SingleNode temp = this.head;
        if (this.head.data > newNode.data) {
            newNode.next = this.head;
            this.setHead(newNode);
            return;
        } else if (this.head.data == newNode.data) {
            System.out.println("该节点以及存在");
            return;
        }
        boolean flag = false;
        while (true) {
            if (temp.next.data > newNode.data) {
                flag = true;
                break;
            } else if (temp.data == newNode.data) {
                System.out.println("该节点以及存在");
                return;
            }
            if (temp.next == null) {
                flag = false;
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            newNode.next = temp.next;
            temp.next = newNode;
        }
    }

    // 单链表反转
    // 1. 时间复杂度O(n) 额外空间复杂度O(n)
    public void reverseOne() {
        if (this.getHead() == null) {
            return;
        }
        Stack<Integer> stack = new Stack<>();
        SingleNode temp = this.getHead();
        while (true) {
            stack.push(temp.data);
            if (temp.next == null) {
                break;
            }
            temp = temp.next;
        }
        temp = this.getHead();
        while (!stack.isEmpty()) {
            temp.data = stack.pop();
            temp = temp.next;
        }
    }

    // 2.时间复杂度O(n) 额外空间复杂度O(1)
    public void reverseSecond() {
        if (this.getHead() == null || this.getHead().next == null) {
            return;
        }
        SingleNode temp = this.getHead();
        SingleNode help = null; // 辅助链表
        SingleNode cur = null;
        while (temp != null) {
            cur = temp.next;
            temp.next = help;
            help = temp;
            temp = cur;
        }
        this.setHead(help);
    }

    /**
     * 合并单链表
     *
     * @param head1
     * @param head2
     */
    public static singleLinked merge(SingleNode head1, SingleNode head2) {
        singleLinked single = new singleLinked();
        if (head1 == null || head2 == null){
            single.setHead(head1 == null ? head2 : head1);
            return single;
        }
        SingleNode head = null;
        head = head1.data <= head2.data ? head1 : head2;
        SingleNode cur1 = head == head1 ? head1 : head2;
        SingleNode cur2 = head == head1 ? head2 : head1;
        SingleNode pre = null; //cur1前一个元素
        SingleNode last = null;// cur2的后一个元素

        while (cur1 != null && cur2 != null){
            if (cur1.data <= cur2.data){
                pre = cur1;
                cur1 = cur1.next;
            }else {
                last = cur2.next;
                pre.next = cur2;
                cur2.next = cur1;
                pre = cur2;
                cur2 = last;
            }
        }
        pre.next = cur1 == null ? cur2 : cur1;
        single.setHead(head);
        return single;
    }


    public static void main(String[] args) {
        singleLinked link = new singleLinked();
        singleLinked head2 = new singleLinked();
        SingleNode node1 = new SingleNode(1);
        SingleNode node2 = new SingleNode(2);
        SingleNode node3 = new SingleNode(3);
        SingleNode node4 = new SingleNode(4);
        SingleNode node5 = new SingleNode(5);
        SingleNode node6 = new SingleNode(6);

        link.add(node1);
        link.add(node4);
        link.add(node5);
        head2.add(node2);
        head2.add(node3);
        head2.add(node6);

//        link.show();
//        link.update(new SingleNode(3));
//
//        link.delete(2);
//        link.show();
//
//        link.queryByData(3);
//        link.queryByData(2);
//        int len = link.getLength();
//        System.out.println(len);
//        link.insert(new SingleNode(7));
//        link.show();
//        link.reverseOne();
//        link.reverseSecond();
//        link.show();
//        head2.show();

        singleLinked merge = singleLinked.merge(link.getHead(), head2.getHead());
        merge.show();


    }

}
